package Algorithm.Tree;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author cj
 * @Date 2022/6/5 12:13
 */
public class bestTopSize2 {

    static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int val) {
            this.value = val;
        }
    }

    class Record {
        public int l;
        public int r;

        public Record(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }

    public int bestTopSize22(Node head) {
        Map<Node, Record> map = new HashMap<>();
        return posOrder(head, map);
    }

    public int posOrder(Node h, Map<Node, Record> map) {
        if (h == null) {
            return 0;
        }
        int ls = posOrder(h.left, map);
        int rs = posOrder(h.right, map);
        // 修改左右子树map信息
        modifyMap(h.left, h.value, map, true);
        modifyMap(h.right, h.value, map, false);
        Record lr = map.get(h.left);
        Record rr = map.get(h.right);
        int lbst = lr == null ? 0 : lr.l + lr.r + 1;
        int rbst = rr == null ? 0 : rr.l + rr.r + 1;
        map.put(h, new Record(lbst, rbst));
        return Math.max(lbst + rbst + 1, Math.max(ls, rs));
    }

    private int modifyMap(Node n, int v, Map<Node, Record> map, boolean s) {
        if (n == null || (!map.containsKey(n))) {
            return 0;
        }
        Record r = map.get(n);
        if ((s && n.value > v) || (!s && n.value < v)) {
            map.remove(n);
            return r.l + r.r + 1;
        } else { // 符合
            int minus = modifyMap(s ? n.right : n.left, n.value, map, s);
            if (s) { // 左子树
                r.r -= minus;
            } else {
                r.l -= minus;
            }
            map.put(n, r);
            return minus;
        }
    }
}
